AGC033 D - Complexity - 競プロ

AGC033 D - Complexity

https://atcoder.jp/contests/agc033/tasks/agc033_d

解答

code: python

h, w = map(int, input().split())

a = list(input()) for _ in range(h)

dp1 = [[k-1 for k in range(w) for _ in range(h)] for _ in range(h)]

dp2 = [[i-1 for i in range(h) for _ in range(w)] for _ in range(w)]

# 初期化

for i in range(h):

ok = [aij for j in range(w)]

for k in range(w - 1, -1, -1):

if k != w - 1 and okk == okk+1:

dp1iik = dp1iik+1

else:

dp1iik = k

for j in range(i + 1, h):

for k in range(w):

if okk != ajk:

okk = ""

for k in range(w - 1, -1, -1):

if okk:

if k != w - 1 and okk == okk+1:

dp1ijk = dp1ijk+1

else:

dp1ijk = k

for k in range(w):

ok = [aik for i in range(h)]

for i in range(h - 1, -1, -1):

if i != h-1 and oki == oki+1:

dp2kki = dp2kki+1

else:

dp2kki = i

for l in range(k + 1, w):

for i in range(h):

if oki != ail:

oki = ""

for i in range(h-1, -1, -1):

if oki:

if i != h-1 and oki == oki+1:

dp2kli = dp2kli+1

else:

dp2kli = i

# 更新

for ans in range(17):

if dp10h-10==w-1:

exit(print(ans))

# dp1:たての切断の分を更新

# dp2:よこの切断の分を更新

# どちらもダブリングの要領で

for i in range(h):

for j in range(i, h):

tmp = dp1ij

for k in range(w):

next_c = tmpk + 1

if next_c < w:

tmpk = tmpnext_c

for k in range(w):

for l in range(k,w):

tmp = dp2kl

for i in range(h):

next_r = tmpi + 1

if next_r < h:

tmpi = tmpnext_r

# dp1:よこの切断の分を更新

# l <= dp1ijk iff j <= dp2kli

# jについて単調性があるのでjごとに尺取り

for i in range(h):

for k in range(w):

l = k-1

for j in range(h-1, i-1, -1):

while l != w-1 and j <= dp2kl+1i:

l += 1

if l > dp1ijk:

dp1ijk = l

# dp2:たての切断の分を更新

# j <= dp2kli iff l <= dp1ijk

# lについて単調線があるのでlについて尺取り

for k in range(w):

for i in range(h):

j = i-1

for l in range(w-1, k-1 ,-1):

while j != h-1 and l <= dp1ij+1k:

j += 1

if j > dp2kli:

dp2kli = j

テーマ

蟻本 2-3 01ナップサック問題その2

メモ

https://atcoder.jp/contests/agc033/submissions/27453026

AtCoder AGC 033 D - Complexity (赤色, 1000 点)

https://www.youtube.com/watch?v=Rr5ul_LDMiw

提出

code: python

h, w = map(int, input().split())

a = list(input()) for _ in range(h)

print(a)

# for i in range(2):

# print(ai == ai+1)

# O(pow(2, 184*2))